package com.zhouxianglh.p23;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 23. 合并K个排序链表
 * <p>
 * 这里借用了冒泡的思路.(解题里的优先级队列 PriorityQueue,性能更好吗?看起来不错)
 *
 * @author zhouxianglh
 */
public class Solution {

    public static void main(String[] args) {
        ListNode[] lists = new ListNode[3];
        // lists[0] = new ListNode(1);
        // lists[0].next = new ListNode(4);
        // lists[0].next.next = new ListNode(5);
        lists[1] = new ListNode(1);
        // lists[1].next = new ListNode(3);
        // lists[1].next.next = new ListNode(4);
        // lists[2] = new ListNode(2);
        // lists[2].next = new ListNode(6);
        System.out.println(mergeKLists(lists));
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || lists.length == 0) {
            return null;
        }
        Arrays.sort(lists, Comparator.comparingInt(a -> {
            if (a != null) {
                return a.val;
            } else {
                return Integer.MAX_VALUE;
            }
        }));
        ListNode node = lists[0];
        ListNode lastNode = node;
        while (null != lists[0]) {
            lists[0] = lists[0].next;
            for (int i = 0, j = lists.length - 1; i < j; i++) {
                if (null == lists[i + 1]) {
                    break;
                } else if (null == lists[i]) {
                    lists[i] = lists[i + 1];
                    lists[i + 1] = null;
                } else if (lists[i].val > lists[i + 1].val) {
                    ListNode temp = lists[i];
                    lists[i] = lists[i + 1];
                    lists[i + 1] = temp;
                } else {
                    break;
                }
            }
            lastNode.next = lists[0];
            lastNode = lists[0];
        }
        return node;
    }

    public static class ListNode {
        int val;

        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
